This invention relates generally to high-speed, broad-band communication networks and, more particularly to the operation of a crossbar switching fabric suitable for communicating data packets in an ATM switch.
High-speed, broad-band communication networks include systems for routing data packets from input sources to output sources. Co-pending U.S. Ser. No. 08/340,493 (incorporated herein by reference) discloses a self routing crossbar switch suitable for use as a switching fabric in an ATM switch.
The basic architecture of prior art systems include an Asynchronous Transfer Mode (ATM), Local Area Network (LAN) using a VLSI-based "Batcher/banyan" switching fabric of the type which has been developed by AT&T/Bellcore. Batcher/banyan switching technology scales to switches larger than 256 ports, and link rates exceeding 1 gigabit/sec. These switches can be interconnected to form a large hierarchial network for supporting large user communities. An example of an actual implementation of a Batcher/banyan switching fabric exists on customized chips from Bellcore (See: A CMOS Batcher and banyan chipset for B-ISDN, p.g. 32-33, William S. Marcus and Jason J. Hickey, ISSCC '90, 1990, IEEE International Solid State Circuit Conference).
Ideally, a Batcher/banyan switching fabric provides parallelism whereby a single port of a Batcher sorting network can feed some number k (typically 2 or 3) banyan routing switches that are connected so that as many as k-cells can be routed to the same number of output ports during the same cell switching cycle without losing any of the data packets. This type of system is described in U.S. Pat. No. 4,893,304, entitled, Broadband Packet Switch With Combined Queuing.
In order to overcome the problem that occurs when more than one data packet is found to be destined to the same output port during the single switch cycle, a "reservation ring" is provided for fairly adjudicating the contention among such conflicting data packets, while permitting at most k of the packets to be presented to the banyan switch in any cycle. Reservation rings resolve output contentions among conflicting data packets, while implementing "fair" access to the output ports of the switching fabric.
Such Batchef/banyan switching fabrics are commonly implemented on customized chips which increases the cost of the ATM switch. Further, in a Batcher/banyan switching fabric it is possible to have multiple paths between sources and destinations which depend on other connections that are present at any particular time. Due to the dependency of one connection to another connection, diagnosing of failures is extremely difficult.
The present invention contemplates a new and improved switching fabric to replace the Batcher/banyan network of prior art systems, reducing the cost to manufacture such systems, provide easier diagnosis of failures in the fabric, simplify design, and for switches of desirable sizes, i.e. up to approximately 256 ports, provide better scaling properties than a Batcher/banyan system. The subject invention can be implemented without change to existing reservation ring mechanisms.